package algorithm_demo.demo05;

/**
 * 从左往右的尝试模型
 * <p>
 * 字符串与数字字符
 * 规定1和A对应、2和B对应、3和C对应…
 * 那么一个数字字符串比如"111"，
 * 就可以转化为"AAA"、“KA"和"AK”。
 * 给定一个只有数字字符组成的字符串str，返回有多少种转化结果
 *
 * @author Api
 * @date 2023/3/12 16:50
 */
public class Code11_ConvertToLetterString {
    public static int number(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        return process(str.toCharArray(), 0);
    }

    //str[0..i-1]已经转化完了，固定了
    //i之前的位置，如何转化已经做过决定了，不用再关心
    //i..有多少种转化的结果
    public static int process(char[] str, int i) {
        if (i == str.length) {//base case
            return 1;
        }
        //i没有到终止位置,0是不能进行转化的
        if (str[i] == '0') {
            return 0;
        }
        //i没有到终止位置
        //str[i]字符不是'0'
        if (str[i] == '1') {
            int res = process(str, i + 1);//i自己作为单独的部分，后续有多少种方法
            if (i + 1 < str.length) {
                res += process(str, i + 2);//(i和i+1)作为单独的部分，后续有多少种方法
            }
            return res;
        }
        if (str[i] == '2') {
            int res = process(str, i + 1);//i自己作为单独的部分，后续有多少种方法
            //(i和i+1)作为单独的部分并且没有超过26，后续有多少种方法
            if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
                res += process(str, i + 2);//（i和i+1）作为单独的部分，后续有多少种方法
            }
            return res;
        }
        //str[i] == '3'-'9'
        return process(str, i + 1);
    }
    /*动态规划*/
    public static int dpWay(String s){
        if (s == null || s.length() == 0){
            return 0;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        //这里可变参数为1个，根据上述的递归可知
        int[] dp = new int[N+1];
        dp[N] = 1;
        //从右向左填写，N已经填写好了，从n-1，到0位置填写即可
        for(int i = N-1; i>=0; i--){
            //所有上述递归return的时刻，就是设置dp[i]的时刻
            //因为数组默认值就是0，所以下列代码可以注释掉
//            if (str[i] == '0') {
//                dp[i] = 0;
//            }
            if (str[i] == '1') {
                dp[i] = dp[i+1];
                if (i + 1 < str.length) {
                    dp[i] += dp[i+2];
                }
            }
            if (str[i] == '2') {
                dp[i] = dp[i+1];
                if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
                    dp[i] += dp[i+2];
                }
            }
        }
        return dp[0];
    }


    public static void main(String[] args) {
        String str = "1111111";
        int number = number(str);
        int number2 = dpWay(str);
        System.out.println(number);
        System.out.println(number2);
    }
}
